import java.io.IOException;
import java.lang.reflect.InvocationTargetException;
import java.math.BigInteger;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2023-05-07
 * Time: 9:22
 */

class A {
    public A(int a) {

    }

    public A(int b, int c) {
        this(b);
    }
}

public class Training {

    /**
     * 牌力初始化
     */
    private static Map<String, Integer> map = new HashMap<String, Integer>() {
        {
            // 匿名内部类创建  由于先初始化在创建 map 对象, 因此无法使用 map.put
            put("3", 3);
            put("4", 4);
            put("5", 5);
            put("6", 6);
            put("7", 7);
            put("8", 8);
            put("9", 9);
            put("10", 10);
            put("J", 11);
            put("Q", 12);
            put("K", 13);
            put("A", 14);
            put("2", 15);
            put("joker", 16);
            put("JOKER", 17);
        }
    };

    /**
     * 斗地主 -- 想通牌类型直接比较  王炸最大
     *
     * @param str 两副牌共同发 中间用 " - " 连接 4 4 4 4-joker JOKER
     */
    public void fightAgainstLandlords(String str) {
        if (str.contains("joker JOKER")) {
            // 王炸一定是组合牌力最大的
            System.out.println("joker JOKER");
        } else {
            String[] strs = str.split("-"); // 分割两副牌
            String[] poker1 = strs[0].split(" "); // 将一副牌取出并除空格
            String[] poker2 = strs[1].split(" ");
            int len1 = poker1.length; // 每副牌的多少
            int len2 = poker2.length;
            // 因为牌已经是排好序了, 如果张数相同 类型相同, 由于已经记录单张牌力, 比较大小即可
            // 同类型的牌对比, 通过总和的大小可以对比 顺子 对子 炸弹 等等 只要牌数相同, 类型一致, 比较字典序大小即可
            if (len1 == len2) {
                int sum1 = 0;
                int sum2 = 0;
                for (String s1 : poker1) {
                    sum1 += map.get(s1);
                }
                for (String s2 : poker2) {
                    sum2 += map.get(s2);
                }
                // 牌之间室友空格的, 因此还需要输出的事原数组
                System.out.println(sum1 > sum2 ? strs[0] : strs[1]);
            } else {
                // 不同类型就剩下
                if (len1 == 4) {
                    // 炸弹
                    System.out.println(strs[0]);
                } else if (len2 == 4) {
                    // 炸弹
                    System.out.println(strs[1]);
                } else {
                    // 啥也不是
                    System.out.println("ERROR");
                }
            }

        }
    }


    /**
     * 2418. 按身高排序
     *
     * @param names   姓名 和 身高一对一
     * @param heights 身高
     * @return 最高的身高的那人的名字
     */
    public String[] sortPeople(String[] names, int[] heights) {
        Integer[] arr = new Integer[names.length];
        for (int i = 0; i < names.length; i++) {
            // 为一个索引数组, 建立好以后对于所有的 i j(i < j) height[i] > height[j]
            arr[i] = i;
        }
        // Comparator 接口是一个函数式接口，
        // 可以使用 Lambda 表达式或匿名内部类来创建 Comparator 对象
        Arrays.sort(arr, (i, j) -> heights[j] - heights[i]); // 索引根据身高降序
        String[] res = new String[names.length];
        for (int i = 0; i < names.length; i++) {
            res[i] = names[arr[i]]; // 根据建立好的索引进行排序
        }
        return res;
    }

    /**
     * 1572. 矩阵对角线元素的和
     *
     * @param mat 正方形矩阵
     * @return 返回对角线之和
     */
    public int diagonalSum(int[][] mat) {
        int n = mat.length; // 行和列
        int sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j || i + j == n - 1) {
                    sum += mat[i][j];
                }
            }
        }
        return sum;
    }

    /**
     * 1662. 检查两个字符串数组是否相等
     *
     * @param word1 数组单词 "ab", "c"
     * @param word2 数组单词 "a", "bc"
     * @return 返回两个单词是否相等
     */
    public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
        int i = 0; // 指向 word1 位置
        int j = 0; // 指向 word2 位置
        int p = 0; // 指向每个单词的字符位置
        int q = 0; // 指向每个单词的字符位置
        int n = word1.length;
        int m = word2.length;
        while (i < n && j < m) {
            // 无论字符长度如何, 但连起来的顺序必须一致
            if (word1[i].charAt(p++) != word2[j].charAt(q++)) {
                return false;
            }
            // 此时某个单词结束, 需要判断并重置 p 指向的单词字符位置
            if (p == word1[i].length()) {
                i++; // 下一个单词
                p = 0; // 重置单词指向
            }

            if (q == word2[j].length()) {
                j++;
                q = 0;
            }
        }
        // 如果一致, 同时走完, 期中一个先走完则表明长度不一致一定不相等
        return i == n && j == m;
    }

    /**
     * 2341. 数组能形成多少数对
     *
     * @param nums 长度为 2 的整数倍的数组
     * @return 多少个数对以及最后数组中剩下几个数字
     */
    public int[] numberOfPairs(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int count = 0;
        for (int arr : nums) {
            if (set.contains(arr)) {
                set.remove(arr);
                count++;
            } else {
                set.add(arr);
            }
        }
        return new int[]{count, set.size()};
    }

    /**
     * 1732. 找到最高海拔
     *
     * @param gain 海拔数组-gain[i] = i 和 i+1 的净海拔高度差
     * @return 最高点海拔(海拔净值)
     */
    public int largestAltitude(int[] gain) {
        // 海拔高度数组中 nums[0] = 0
        // nums[i] = gain[i-1] + nums[i-1]
        int[] nums = new int[gain.length + 1];
        nums[0] = 0;
        int max = 0;
        for (int i = 1; i < nums.length; i++) {
            nums[i] = nums[i - 1] + gain[i - 1];
            max = Math.max(max, nums[i]);
        }
        return max;
    }

    /**
     * 特殊情况下, arr[] = {1}; 算严格递增, 不用操作
     * 1827. 最少操作使数组递增
     *
     * @param nums 下标从0开始的整数数组
     * @return 返回让nums 变为严格递增数组的最小操作次数
     */
    public int minOperations(int[] nums) {
        int count = 0;
        if (nums.length == 1) {
            return 0;
        }
        for (int i = 1; i < nums.length; i++) {
            if (nums[i - 1] >= nums[i]) {
                count += (nums[i - 1] - nums[i] + 1);
                nums[i] = nums[i - 1] + 1;
            }

        }
        return count;
    }

    /**
     * 2185. 统计包含给定前缀的字符串
     *
     * @param words 单词数组
     * @param pref  前缀字符
     * @return 前缀相同的单词数目
     */
    private static int prefixCount(String[] words, String pref) {
        int count = 0;
        for (String str : words) {
            if (str.length() < pref.length()) {
                continue;
            }
            if (str.substring(0, pref.length()).equals(pref)) {
                count++;
            }
        }
        return count;
    }

    /**
     * 删除公共字符串
     *
     * @param src 要删除的字符串
     * @param del 公共字符串
     */
    public void deleteChar(String src, String del) {
        HashSet<Character> set = new HashSet<>();

        for (int i = 0; i < del.length(); i++) {
            set.add(del.charAt(i));
        }

        for (int i = 0; i < src.length(); i++) {
            if (!set.contains(src.charAt(i))) {
                System.out.print(src.charAt(i));
            }
        }
    }

    /**
     * 组队竞赛
     *
     * @param n 多少组, 一组三个人
     *          一组三人中, 第二高的那个人为中值, 求这些人中如何组合让中值最大
     */
    public void competition(int n) {
        Scanner scan = new Scanner(System.in);
        long[] arr = new long[n * 3];
        for (int i = 0; i < 3 * n; i++) {
            arr[i] = scan.nextLong();
        }
        long max = 0;
        Arrays.sort(arr);
        // 排序结束后, 一定是第二大和第三大的数
        for (int i = 0; i < n; i++) {
            // 每次取排序后中间的那个数即可
            max += arr[(arr.length - 2 * (i + 1))];
        }
        System.out.println(max);
    }


    /**
     * 双指针思路
     *
     * @param str 给定的字符串
     * @return 返回最长的数字字符串
     */
    public static String LongStr(String str) {
        // 双指针思想
        int maxLen = 0;
        int count = 0;
        int end = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
                count++;
                if (maxLen < count) {
                    maxLen = count;
                    end = i; // 重置尾
                }
            } else {
                // 不是数字字符重置长度
                count = 0;
            }

        }
        return str.substring(end - maxLen + 1, end + 1);
    }


    /**
     * 投票法
     *
     * @param numbers 整形数组
     * @return 返回出现最做的那个数
     */
    public int MoreNumber(int[] numbers) {
        int count = 1; // 以第一个元素为基准
        int temp = numbers[0];

        for (int i = 1; i < numbers.length; i++) {
            if (numbers[i] == temp) {
                count++;
            } else {
                count--;
            }
            if (count == 0) {
                // 以下一个元素为基准
                temp = numbers[i];
                count = 1; // 重置票数
            }
        }
        return temp;
    }

    /**
     * 4.1
     * 统计回文
     *
     * @param s1 原字符串
     * @param s2 需要插入的字符串
     * @return 返回 s2 插入 s1 中有几种回文情况
     */
    public int isMoslems(String s1, String s2) {
        int count = 0;
        for (int i = 0; i < s1.length() + 1; i++) {
            // 一共有 s1.length() + 1 种插入方式
            // substring(a,b) [a,b) // 左闭又开
            String str = s1.substring(0, i) + s2 + s1.substring(i, s1.length());
            // 判断回文
            StringBuffer sb = new StringBuffer(str);
            if (sb.reverse().toString().equals(str)) {
                count++;
            }
            long a = Long.MAX_VALUE;
        }
        return count;
    }

    /**
     * 4.2
     * 判断连续最大额和  -1 2, 1 最大连续和为 3
     *
     * @param n 一共有多少个数
     */
    public void continuesMaxSum(int n) {
        Scanner scan = new Scanner(System.in);
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scan.nextInt();
        }
        int max = Integer.MIN_VALUE; // 用来表示负数中的最大数
        int thisMax = 0; // 用于记录本次最大数
        int maxSum = 0;
        int count = 0; // 统计负数
        for (int i = 0; i < n; i++) {
            if (arr[i] < 0) {
                count++;
                if (arr[i] > max) {
                    max = arr[i]; // 更新最大的负数;
                }
            }
            thisMax += arr[i]; // 统计本次最大数
            if (thisMax > maxSum) {
                maxSum = thisMax; // 最大和更新
            }
            if (thisMax < 0) {
                thisMax = 0; // 清空
            }
        }
        if (count == n) {
            System.out.println(max);
        } else {
            System.out.println(maxSum);
        }
    }

    /**
     * 相邻两块蛋糕之间欧几里得距离不能为 2 -- 开方后为 2  因此行列都不能刚好为 2
     *
     * @param row 行数
     * @param col 列数
     */
    public void twoEuclid(int row, int col) {
        Scanner scan = new Scanner(System.in);
        int[][] arr = new int[row][col];
        // 左上角的第一个一定可以放一块蛋糕
        // 以左上角第一块为出发点 直线欧几里得距离只有垂直或水平距离上为 2 其余不可能
        // 因此推断第一行 1 1 0 0
        //  推断第二行   1 1 0 0
        // 推断第一列 1 1 0 0
        // 推断第二列 1 1 0 0
        // 结论 横纵都为 4 一个周期
        // 1 1 0 0
        // 1 1 0 0
        // 0 0 1 1
        // 0 0 1 1
        int count = 0;
        for (int i = 0; i < row; i++) {
            if (i % 4 == 0 || i % 4 == 1) {
                // 判断横向周期
                for (int j = 0; j < col; j++) {
                    if (j % 4 == 0 || j % 4 == 1) {
                        arr[i][j] = 1;
                    }
                }
            } else {
                // 判断列向周期
                for (int j = 0; j < col; j++) {
                    if (j % 4 == 2 || j % 4 == 3) {
                        arr[i][j] = 1;
                    }
                }
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (arr[i][j] == 1) {
                    count++;
                }
            }
        }
        System.out.println(count);
    }


    /**
     * @param str 字符串  + - 只能出现在开头. 只能有数字字符
     * @return 符合要求的数字或者0
     */
    public int StrToInt(String str) {
        boolean flag = false;
        int num = 0;
        for (int i = 0; i < str.length(); i++) {
            // 判断开头第一个字符是否符合
            if (i == 0 && (str.charAt(0) == '+' || str.charAt(0) == '-')) {
                // 判断是否为负数特殊情况 标记负号
                if (str.charAt(0) == '-') {
                    flag = true;
                }
            } else {
                // 此处首位字符必然符合要求
                // 其余情况 -- 排除出现a-z
                if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
                    // 存储数值并累加
                    num = (num * 10 + (str.charAt(i) - '0'));
                    // 字符串长度为 0 - 100, 可能累加可能超
                } else {
                    // 任意位置出现字母或者首位不是 + -
                    return 0;
                }
            }
        }
        return flag == true ? num * (-1) : num;
    }

    public int fun2(String str) {
        boolean flag = false; // 负数标志位
        int sum = 0; // 计数和
        for (int i = 0; i < str.length(); i++) {
            // 判断首字符是否合法
            if (i == 0 && str.charAt(0) == '+' || str.charAt(0) == '-') {
                // 标记负数

                if (str.charAt(0) == '-') {
                    flag = true;
                }
            } else {
                // 没有出现 + -
                // 判断是否出现字母
                if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
                    // 是数字字符
                    // 转换数字字符
                    sum = (sum * 10 + (str.charAt(i) - '0')); // 变为 int 类型
                } else {
                    // 非数字字符
                    return 0;
                }
            }
        }
        return flag == true ? sum * (-1) : sum;
    }

    /**
     * 只有左括号右括号 出现其他或匹配不上一律错误
     *
     * @param str 字符串
     * @param n   字符串长度
     * @return 返回是否匹配
     */
    public boolean chkParenthesis(String str, int n) {
        // write code here
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            // 左括号入队列
            if (str.charAt(i) == '(') {
                stack.add(str.charAt(i));
            } else {
                // 非左括号 ) 或者 字符
                // 入股此时队列为空, 来的是 ) 或者 字符则错误
                if (!stack.empty() && str.charAt(i) == ')') {
                    // 弹出栈顶元素即弹出一个左括号
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        if (stack.empty()) {
            return true;
        } else {
            return false;
        }
    }

    /**
     * 最小步数生成斐波那契额数
     *
     * @param n 15
     * @return 8 13 21 因此最小斐波那契额数为 15-13 两步
     */
    private static int fibNumber(int n) {
        int a = 1;
        int b = 1;
        int tmp = 0;
        for (int i = 0; i < 1_000_000; i++) {
            tmp = a + b; // a = 8  b = 13
            a = b; // a = 13
            b = tmp; // b = 21
            if (tmp > n) {
                // ret = 8 + 13 = 21
                break;
            }
        }
        return (n - a) > (tmp - n) ? (tmp - n) : (n - a);
    }

    /**
     * @param arr 字符串数组
     * @return 返回什么数组中的单词以什么方式排序
     */

    // 判断字符串排序情况
    private static String sortWord(String[] arr) {
        boolean flag1 = dictionarySort(arr);
        boolean flag2 = lengthSort(arr);
        if (flag1 && flag2) {
            return "both";
        } else if (flag1) {
            return "lexicographically";
        } else if (flag2) {
            return "lengths";
        } else {
            return "none";
        }
    }

    /**
     * @param words 单词数组
     * @return 返回是否为字典序排序
     */
    // 判断字典序
    private static boolean dictionarySort(String[] words) {
        for (int i = 1; i < words.length; i++) {
            if (words[i - 1].compareTo(words[i]) > 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * @param words 单词数组
     * @return 返回是否为长度排序
     */
    // 判断长度排序
    private static boolean lengthSort(String[] words) {
        for (int i = 1; i < words.length; i++) {
            if (words[i - 1].length() > words[i].length()) {
                return false;
            }
        }
        return true;
    }

    /**
     * 返回 a b 的最小公倍数
     *
     * @param a 整数 a
     * @param b 整数 b
     */
    private void GCD(int a, int b) {
        int max = Math.max(a, b);
        // 最大不超过二者乘积(最大公约数 > 1 下), 最小公倍数 * 最大公约数 = a * b;
        for (int i = max; i <= a * b; i++) {
            if (max % a == 0 && max % b == 0) {
                System.out.println(max);
                break;
            }
            max++;
        }
    }


    /**
     * 只能向右或者向下
     *
     * @param m 横
     * @param n 列
     * @return 返回从左上角到右下角的最小步数
     */
    // 定义状态 f(i, j) 表示(0, 0)左上角到点(i,j) 的路径数
    // 初始化 对于第一行和第一列的所有点只能向右或向下, 所以到达(i,j) 的数量路径都为1
    //                                           f(i, 0) = 1  f(0, j) = 1
    // 状态转移方程: 对于其他点, 只能向下或者向右, 所以到达点(i,j) 的路径数量为
    //                               f(i, j-1)  + f(i-1, j)
    // 终止状态, 到达右下角 f(n-1, m-1)
    private static int uniquePath(int m, int n) {
        // 因为是方格, 而且是节点
        m++;
        n++;
        int[][] array = new int[m][n];
        // 初始化第一行
        for (int i = 0; i < m; i++) {
            array[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            array[0][j] = 1;
        }
        // 计算其他点的路径数量
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                array[i][j] = array[i - 1][j] + array[i][j - 1];
            }
        }
        // 返回到达右下角的路径数量
        return array[m - 1][n - 1];
    }

    /**
     * // 此处的用法为不考虑无符号整形情况下, 否则需要用 long 来承接
     *
     * @param a 1
     * @param b 2
     * @return 返回不用 + 运算的 加法结果
     */
    public int addAB(int a, int b) {
        int c = a ^ b; // 按位相加
        int d = (a & b) << 1; // 计算进位量
        // 0 0 1 1
        // 0 0 0 1
        //         c : 0 0 1 0
        //         d : 0 0 0 1 - > 左移 d : 0 0 1 0
        while (d != 0) {
            a = c;
            b = d;
            c = a ^ b;
            d = (a & b) << 1;
        }
        return c;
    }

    /**
     * 寻找最近公共祖先, 满二叉树点从 1 开始编号
     *
     * @param a 整数
     * @param b 整数
     * @return 最近的公共祖先, 也有可能是它自己
     */
    public int getLCA(int a, int b) {
        // write code here
        // i 节点的父节点 = i / 2
        if (a == b) {
            return a;
        }

        return a > b ? getLCA(a / 2, b) : getLCA(a, b / 2);
    }

    /**
     * 求最大连续 bit 数
     *
     * @param n 整数
     */
    public void continueBit(int n) {
        String str = Integer.toBinaryString(n); // 将一个整数转为二进制字符串
        String[] array = str.split("0"); // 按照 0 分割
        // PS : 如果分隔符位于开头或者结尾, 那么会用空字符串替换并包含在结果数组中
        int max = -1;
        for (String s : array) {
            if (s.length() > max) {
                max = s.length();
            }
        }
        System.out.println(max);
    }

    /**
     * 幸运数 : sum > multi
     *
     * @param a     为 Array.sort 后的数组
     * @param index 下标位置
     * @param sum   前几个数求和
     * @param multi 前几个数乘积
     * @return 有多少个幸运数
     */
    private static int isLuckyNumber(int[] a, int index, long sum, long multi) {
        int count = 0;
        for (int i = index; i < a.length; i++) {
            sum += a[i]; // 计算和
            multi *= a[i]; // 计算乘积
            if (sum > multi) {
                // 统计幸运数, 并且指向下一个可以成为幸运数
                count = count + 1 + isLuckyNumber(a, i + 1, sum, multi);
                // 1 1   1 1 > 1 * 1
                // 1 1 1 1 1 1 = 3 > 1 * 1 * 1
            } else if (a[i] == 1) {
                // 中途遇到 1, 有可能不会让和大于乘积, 但需要保留,并往下找
                count = count + isLuckyNumber(a, i + 1, sum, multi);
            }
            // 重置和 以及 乘积
            sum -= a[i];
            multi /= a[i];
            for (; i < a.length - 1 && a[i] == a[i + 1]; i++) {
                // 相同号码的求是无区别的
            }
        }
        return count;
    }

    /**
     * 将具体的日期 XX 年 XX 月 XX 日转为具体的今年的第多少天
     *
     * @param year  年份
     * @param month 月份
     * @param day   天数
     */
    public void changeDays(int year, int month, int day) {
        int time = 0;
        int[] arr = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        if (isLeapYear(year)) {
            arr[1] = 29;
        }
        for (int i = 0; i < month - 1; i++) {
            time += arr[i];
        }
        System.out.println(time + day);
    }

    /**
     * @param year 年份
     * @return 返回是否为闰年
     */
    private static boolean isLeapYear(int year) {
        if (year % 100 != 0 && year % 4 == 0) {
            return true;
        }
        return false;
    }


    /**
     * 判断 1- n 内有几个数为完美数
     *
     * @param n 1 < n < 5 * 10^5
     */
    public void PerfectNumber(int n) {
        int count = 0;
        for (int i = 1; i < n - 1; i++) {
            if (isPerfectNumber(i)) {
                count++;
            }
        }
        System.out.println(count);
    }

    /**
     * 完美数 : 自身真因子之和为本身 例如 28 真因子为 1 2 4 7 14 28 除了本身28外 1 2 4 7 14 之和为 28 因此为完美数
     *
     * @param n 当前这个数
     * @return 返回是否为完美数
     */
    private static boolean isPerfectNumber(int n) {
        int count = 0;
        for (int i = 1; i < n - 1; i++) {
            if (n % i == 0) {
                count += i;
            }
        }
        if (count == n) {
            return true;
        }
        return false;
    }

    public void fun3() {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        String a = scan.nextLine();
        if (n <= 2) {
            System.out.println(-1);
            return;
        }
        int[][] array = new int[n][2 * (n - 1) + 1]; // 列数可以观察, 但是行数一定和 n 一致
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 2 * i + 1; j++) {
                if (j == 0 || j == 2 * (n - 1)) {
                    // 第一列和最后一列
                    array[i][j] = 1;
                } else if (j == 1) {
                    // 第二列
                    array[i][j] = array[i - 1][j] + array[i - 1][j - 1];
                } else {
                    // 观察可以看到, 每次从中间向两边扩, 该数的中间 左上 右上的位置分别为 j-2 j-1 j
                    array[i][j] = array[i - 1][j - 2] + array[i - 1][j - 1] + array[i - 1][j];
                }
                // 判断是否有偶数
                if (i == n - 1 && array[i][j] % 2 == 0) {
                    // i = n - 1 判断当前这行就是所求哪行
                    System.out.println(j + 1); // j 从 0 开始
                    return;
                }

            }
        }
    }

    public void yangHui() {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int n = scan.nextInt();
            if (n <= 2) {
                System.out.println(-1);
            } else if (n % 2 == 1) {
                System.out.println(2);
            } else if (n % 4 == 0) {
                System.out.println(3);
            } else {
                System.out.println(4);
            }
        }
    }


    private static int maxLenCharString(String str1, String str2) {
        String maxStr = str1.length() > str2.length() ? str2 : str1; // 保证为公共串
        String minStr = str1.length() > str2.length() ? str1 : str2; // 保证为匹配出
        System.out.println(maxLenCharString(minStr, maxStr));

        // aaabbbb
        // aabaaacbbbb  此时匹配的最长公共子串数目就为 4
        // 采取两头缩进遍历
        // asdfas  werasdfaswer
        // asdfas asdfa asdf asd as a 第一次
        // sdfas sdfa sdf sd s 第二次
        // dfas dfa df d 第三次 ....
        int maxLen = 0;
        // 头指针从第一位开始递增
        // 尾指针从最后一位开始递减
        // 第一次寻找到的集合一定是最大的

        for (int i = 0; i < minStr.length(); i++) {
            for (int j = minStr.length(); j > i; j--) {
                if (maxStr.contains(maxStr.substring(i, j))) {
                    // 更新 maxLen 的最大值
                    maxLen = Math.max(j - i, maxLen);
                }
            }
        }
        return maxLen;
    }

    String arr = new String("goods");

    public void fun(String s) {
        s = "test OK";
    }


    /**
     * 固定滑动窗口法
     * MP3 光标位置
     *
     * @param s 输入的指令  UUUDDD
     * @param n 歌曲数目
     */
    private static void MP3_Index(String s, int n) {
        // 滑动窗口 -- 固定长度为 4, 把无法显示到页面的内容都放到长度无限的页面上
        // 模拟可以知道, 当前位置为 i 时, U 操作光标向上一个位置 (i - 1 - 1 + n) % n + 1
        // D 操作光标向后一个位置 i % n + 1

        // 规定起始位置为 1
        int start = 1;
        // 页面末位置, 如果页面的歌曲数目小于 4返回当前小于 4 的歌曲数目
        int end = Math.min(n, 4);
        // 光标初始位置, 位置都从 1 开始, 用于固定窗口的位置
        int index = 1;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'U') {
                // 改变当前光标位置
                index = (index - 1 - 1 + n) % n + 1;
            } else if (s.charAt(i) == 'D') {
                index = index % n + 1;
            }

            // 执行一步过后, 判断是否需要翻页
            if (index < start) {
                // 光标在窗口上面, 比如 1 2 3 4 当前在 1 U操作
                start = index;
                end = start + 3;
            } else if (index > end) {
                // 光标在当前固定窗口的下面
                end = index;
                start = end - 3;
            }
        }
        for (int i = start; i <= end; i++) {
            System.out.print(i + " ");
        }
        System.out.println(); // 换行
        System.out.println(index); // 光标位置
    }

    public static void main5(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt(); // 表示有几组牌需要洗
        for (int i = 0; i < T; i++) {
            int n = scan.nextInt(); // 上半堆和下半堆得牌数 2n为总牌数
            int k = scan.nextInt(); // 洗牌次数
            // 利用顺序表存储
            ArrayList<Integer> cards = new ArrayList<>(); // 原牌组
            ArrayList<Integer> list1 = new ArrayList<>(); // 上半牌组
            ArrayList<Integer> list2 = new ArrayList<>(); // 下半牌组
            for (int j = 0; j < 2 * n; j++) {
                // 给原牌组初始化
                cards.add(scan.nextInt());
            }
            // 颠倒排序, 利于后续洗牌 == 先放左手后放右手
            Collections.reverse(cards);
            // 模拟洗牌
            for (int x = 0; x < k; x++) {
                // 下一次分牌前清空手上分好的牌, 避免错误读取
                list1.clear();
                list2.clear();
                // 分牌 由于已经颠倒牌序, 此时下半堆牌在左手放list1中
                for (int j = 0; j < n; j++) {
                    list1.add(cards.get(j));
                }
                // 分牌 上半堆在右手
                for (int j = n; j < 2 * n; j++) {
                    list2.add(cards.get(j));
                }
                // 下一次牌组进来前给当前手上的牌清空避免添加在后面获取错误数据
                cards.clear();
                // 洗牌
                for (int j = 0; j < n; j++) {
                    // 先添加下半堆 即左手list1
                    cards.add(list1.get(j));
                    cards.add(list2.get(j));
                }
            }
            // 原本正常的顺序洗牌后颠倒 还需从后向前输出
            // 此时给原本颠倒的牌在翻转成正常排序
            Collections.reverse(cards);
            // 输出牌序, 链表按照数组形式输出, 带有 [] 以及逗号
            System.out.println(cards.toString()
                    .replace("[", "")
                    .replace("]", "")
                    .replace(",", ""));
        }
        scan.close();
    }

    /**
     * @param m 整数 m 比 n 大
     * @param n 整数 你
     * @return 返回最大公约数
     */
    private static int common_divisor(int m, int n) {
        // 此时的 n 必定大于 m 因为打不过
        // 辗转相除
        while (n != 0) {
            int k = m % n;
            // 更新
            m = n;
            n = k;
        }
        return m;
    }

    /**
     * 输出字符串中第一次出现的唯一的字符
     *
     * @param s 字符串
     */
    public void uniqueNumber(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                // 此时已经有该字符了, 将其对应 value 设为 1
                map.put(s.charAt(i), 1);
            } else {
                // 第一次添加该字符
                map.put(s.charAt(i), 0);
            }
        }
        // 相同顺序遍历, 保证第一个输出的 0 是唯一的字符
        for (int i = 0; i < s.length(); i++) {
            if (map.get(s.charAt(i)) == 0) {
                // 说明只有一个该字符
                System.out.println(s.charAt(i));
                return;
            }
        }
        // 没有唯一字符
        System.out.println(-1);
    }

    /**
     * TODO : 投票法或者哈希法
     *
     * @param gifts 数组
     * @param n     素组元素个数
     * @return 返回出现此处超过一半的那个数
     */
    public int getValue(int[] gifts, int n) {
        // write code here
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < gifts.length; i++) {
            int money = gifts[i];
            if (map.get(money) == null) {
                // 第一次出现
                map.put(gifts[i], 1);
            } else {
                // 不是第一次出现, 获取对应的出现次数
                int count = map.get(money);
                // 需要加上本身出现的这次
                if (count + 1 > n / 2) {
                    return money;
                }
                // 如果重复, 并且 count 也还没超过 n / 2
                if (count != 0) {
                    map.put(money, count + 1);
                }
            }

        }
        return 0;
    }

    /**
     * 两个字符串之间的最小编辑距离 - 删除, 替换, 新增等都算一次操作
     *
     * @param str1 字符串
     * @param str2 字符串
     */
    private void editor(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        int[][] dp = new int[m + 1][n + 1];
        // 初始桩体方程
        for (int i = 1; i <= m; i++) {
            // 两个字符串最前面插入一个空字符
            dp[i][0] = i;
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = j;
        }
        // 状态转移
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 字符型相同情况下, 无需编辑操作
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
            }
        }
        System.out.println(dp[m][n]);
    }


    /**
     * 回溯算法
     * 迷宫问题
     */
    private static List<int[]> ans = new ArrayList<>();
    private static List<int[]> path = new ArrayList<>();

    public static void main4(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[][] maze = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    maze[i][j] = sc.nextInt();
                }
            }
            //深度优先搜索
            dfs(maze, 0, 0);
            for (int[] arr : ans) {
                System.out.println("(" + arr[0] + "," + arr[1] + ")");
            }
            //清空路径path，结果集ans，实际ans指向新建对象，无需清空
            path.clear();
            ans.clear();
        }
    }

    private static void dfs(int[][] maze, int i, int j) {
        //结束条件，一定要用路径新建集合，path最后会remove为空
        if (i == maze.length - 1 && j == maze[0].length - 1) {
            path.add(new int[]{i, j});
            ans = new ArrayList<>(path);
            return;
        }
        //边界条件，剪枝
        if (i < 0 || i >= maze.length || j < 0 || j >= maze[0].length || maze[i][j] == 1) return;

        //i,j加入集合,并且当前位置设置为障碍
        path.add(new int[]{i, j});
        maze[i][j] = 1;
        //向四个方向递归
        dfs(maze, i + 1, j);
        dfs(maze, i, j + 1);
        dfs(maze, i - 1, j);
        dfs(maze, i, j - 1);
        //找到死胡同，回溯，撤销i,j选择，当前位置设置为可走
        path.remove(path.size() - 1);
        maze[i][j] = 0;
    }

    /**
     *
     */

    /**
     * @param board 二维数组
     * @return 返回最大年终奖, 保证每个礼物大于 100 并小于 1000
     */
    public int getMost(int[][] board) {
        // write code here
        int n = board.length;
        int[][] dp = new int[n][n];
        dp[0][0] = board[0][0];
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + board[0][i];
            dp[i][0] = dp[i - 1][0] + board[i][0];

        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + board[i][j];
            }
        }
        return dp[n - 1][n - 1];
    }


    /**
     * 星际密码 - 牛客
     */
    public void Orion_s_Key() {
        int[] arr = new int[10001]; // 从1开始算
        arr[1] = 1; // 斐波那契数列
        arr[2] = 2;
        // 将全部结果计算后放于 arr 数组中
        for (int i = 3; i < 10001; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
            arr[i] = arr[i] % 10000;
        }
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            StringBuffer sb = new StringBuffer();
            int n = scan.nextInt();
            // 遍历 n 之前的所有结果
            for (int i = 0; i < n; i++) {
                int x = scan.nextInt();
                sb.append(String.format("%04d", arr[x]));
            }
            System.out.println(sb);
        }
    }

    /**
     * 数根 - 牛客
     */
    private void rootNumber() {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            String s = scan.nextLine(); // 直接用long无法装下该长度的整型
            while (s.length() > 1) {
                char[] ch = s.toCharArray();
                int num = 0;
                for (int i = 0; i < ch.length; i++) {
                    num += ch[i] - '0'; // 转为整数
                }
                // 将 num 转为字符, 观察是否相加为个位数.
                s = String.valueOf(num); //
            }
            System.out.println(s);
        }
    }

    /**
     * 一次只能上一级或两级
     *
     * @param target 第 target 级台阶
     * @return 返回跳上 target 级台阶一共多少种方法
     */
    public int jumpFloorII(int target) {
        // f(n) = f(n-1) + f(n-2)
        // n 级台阶
        // f(n) = f(n-1) + f(n-2) + f(n-3)+ f(n-n)
        // 即一共n级的台阶, 有 n-1级的跳法 加上 n-2级的跳法 加上 n-3级的跳法
        if (target == 1) {
            return 1;
        }
        int[] array = new int[target + 1]; // 加一步到顶
        // 0级 和 1级 都只有一种方法
        array[0] = 1; // 虽然是 0 级还需要网上跳一级到顶
        array[1] = 1; // 虽然 1 级 直接跳2步到顶
        for (int i = 2; i < target + 1; i++) {
            int count = 0;
            for (int j = 0; j < i; j++) {
                count += array[j];
            }
            array[i] = count; // 统计当前台阶的跳法
        }
        return array[target];
    }

    /**
     * 判断三边是否形成 三角形
     */
    public static void sanjiao() {
        Scanner scan = new Scanner(System.in);
        // 注意到 c 的范围非常非常的大, 采用整型大数字的处理类
        BigInteger a, b, c;
        while (scan.hasNext()) {
            boolean flag = true; // 放内部重置 flag
            a = scan.nextBigInteger();
            b = scan.nextBigInteger();
            c = scan.nextBigInteger();
            if ((a.add(b)).compareTo(c) <= 0)
                flag = false;
            if ((a.add(c)).compareTo(b) <= 0)
                flag = false;
            if ((b.add(c)).compareTo(a) <= 0)
                flag = false;
            if (flag) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }

    /**
     * 给定两个整数, 不用加减乘除实现两数相加
     */
    public int Add(int num1, int num2) {
        while (num2 != 0) {
            // 两位数按位与得到要进位的位数
            int tmp = (num1 & num2) << 1;
            // 两位数异或相当于不进位相加
            num1 ^= num2;
            num2 = tmp;
        }
        return num1;
    }

    /**
     * 翻转部分节点
     */
    public void partReserveNode() {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(); // 节点个数
        listNode head = new listNode(-1); // 建立伪头结点
        listNode cur = head;
        // 初始化节点
        for (int i = 0; i < n; i++) {
            listNode node = new listNode(scan.nextInt());
            cur.next = node; // 指向下一个新节点
            cur = cur.next; // 向后移动指向当前最后一个节点
        }
        int leftIndex = scan.nextInt(); // 输入左端点
        int rightIndex = scan.nextInt(); // 输入右端点

        // 记录找到后的端点对应的节点位置
        listNode startNode = head;
        listNode endNode = head;

        // 遍历寻找左端点, 从 1 开始, 下标从 0 开始, 因此为 leftIndex - 1
        // 当前有一个虚拟头结点
        for (int i = 0; i < leftIndex - 1; i++) {
            startNode = startNode.next;
        }

        // 遍历寻找右端点
        for (int i = 0; i <= rightIndex; i++) {
            endNode = endNode.next;
        }

        // 翻转节点
        // 需要先记录左右端点的下一个节点
        listNode firstNode = startNode.next; // 记录左端点的下一个节点
        listNode lastNode = endNode; // 记录右端点当前节点

        int count = rightIndex - leftIndex + 1; // 判断中间有几个节点
        while (count-- != 0) {
            listNode prevNode = new listNode(firstNode.val); // 前驱节点
            prevNode.next = lastNode;
            lastNode = prevNode;
            firstNode = firstNode.next;
        }
        // 连接 left 前面的节点
        startNode.next = lastNode;
        head = head.next; // 去掉虚拟头节点
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }


    /**
     * 猴子粉桃
     */
    public void monkeyPeach() {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int n = scan.nextInt();
            if (n == 0)
                break;
            long a = (long) Math.pow(5, n);
            long b = (long) Math.pow(4, n);
            System.out.println((a - 4) + " " + (b - 4 + n));
        }
    }

    /**
     * 正数数组中的最小不可组成和
     * 输入：正数数组arr
     * 返回：正数数组中的最小不可组成和
     */
    public int getFirstUnFormedNum(int[] arr) {
        if (arr == null || arr.length == 0) return 0;

        // 只有一个元素在区间[min, max]上, 如果所有的数都可以被arr 某一个子集相加得到
        // 那么 max + 1 是 arr 的最小不可组成和
        if (arr.length == 1) return arr[0] + 1;

        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            max += arr[i]; // 计算每个容量的总和价格
            min = Math.min(arr[i], min); // 记录当前最小值
        }
        int[] dp = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            // dp 数组从后向前初始化
            for (int j = max; j >= arr[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - arr[i]] + arr[i]);
            }
        }

        for (int i = min; i < max; i++) {
            if (dp[i] != i) return i;
        }
        return max + 1;
    }


    /**
     * 二分思想找假币. 假币轻, 最快时间找出找出假币, 并返回称量此处.
     * 天平上左右两边可以放无限的币
     */
    public void find_counterfeit_money() {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int n = scan.nextInt();
            if (n == 0) break;
            // n = 1, 它就是假币, 称量0次
            // n = 2, 称量1次, 两端不平,
            // n = 3, 称量1次, 称量相等另一张假币, 否则称上轻的假币
            // n = 4, 称量2次, 第一次两张相等. 第二次称另外两张出结果
            // n = 5, 称量2次, 第一次称两张相等, 第二次称两张相等或者其中一张轻
            // n = 6, 称量2次, 第一次左右称三张, 拿出轻的那三张重中的两张进行称量,相等为另一张

            int count = 0;
            while (n >= 2) {
                n = (int) Math.ceil((double) n / 3);
                count++;
            }
            System.out.println(count);
        }
    }

    /**
     * 输入一个整数, 可以分解为一个或者多个数组的积
     * 36 = 2 * 2 * 3 * 3
     */
    public void fun() {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int count = 0;
            for (int i = 2; i <= Math.sqrt(n); i++) {
                // 30 % 2
                if (n % i == 0) {
                    while (n % i == 0) {
                        // 15 % 2 = 1

                        // 30 / 2 = 15
                        n /= i;

                    }
                    count++;
                }

            }
            // 最终整除了各个因子数之后剩余的数字不为1则本身也是一个因子，因此因子数+1
            if (n != 1) {
                count++;
            }
            System.out.println(count);
        }
    }

    /**
     * 第 n 个泰波那契数
     */
    public int tribonacci(int n) {

        // 处理边界值
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;

        // 1. 创建 dp 表
        int[] dp = new int[n + 1];

        // 2. 初始化
        dp[0] = 0;
        dp[1] = dp[2] = 1;

        // 3. 填写 dp 表
        for (int i = 3; i <= n; i++) {
            // 根据状态转移方程填写 dp 表
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

        // 4. 确定返回值
        return dp[n];
    }

    /**
     * 上楼梯最小花费问题
     *
     * @param cost
     * @return
     */
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;

        // 1. 创建 dp 表
        int[] dp = new int[n + 1];

        // 2. 初始化
        dp[0] = dp[1] = 0;

        // 3. 填写 dp 表
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        // 4. 确定返回值
        return dp[n];
    }

    /**
     * 不同路径问题
     *
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {

        // 1. 创建 dp 表
        // 注意多开了一行一列.
        int[][] dp = new int[m + 1][n + 1];

        // 2. 初始化
        // 确保起始点为 1. 保证起始点的上一个位置或者前一个位置为 1即可正确填写后续 dp 表
        dp[0][1] = 1; // 我选择原本矩阵起始点的上一个点.
        // dp[1][0] = 1; // 也可以选择原本矩阵起点的前一个点

        // 3. 填写 dp 表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 根据状态转移方程进行填表
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }

        // 4. 确认返回值
        return dp[m][n];
    }

    /**
     * 最小下降路径和
     *
     * @param matrix
     * @return
     */
    public int minFallingPathSum(int[][] matrix) {

        // 1. 建立 dp 表
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m + 1][n + 2];

        // 2. 初始化
        // 第一行初始化为 0
        // 第一列和最后一列初始化为无穷大
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i][n + 1] = Integer.MAX_VALUE;
        }

        // 3. 填写 dp 表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 需要注意, 没有三个参数的最小值方法
                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j + 1]))
                        + matrix[i - 1][j - 1];
            }
        }

        // 如果为默认为 0, 第一次比较 dp[m][j] 为正值时会影响最小取值
        int taget = Integer.MAX_VALUE; // 为最大值才不会影响最小值取值

        // 4. 确认返回值
        for (int j = 1; j <= n; j++) {
            taget = Math.min(taget, dp[m][j]);
        }

        return taget;
    }


    /**
     * 最小下降路径和
     *
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {

        // 1. 创建 dp 表
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m + 1][n + 1];

        // 防止后续初始化 dp[1][0] 或者 dp[0][1] 时越界
        // 此处只能用 &&, 当 m = 1 或 n = 1时, 只能代表该二维数组为一行或一列
        // 一行时, 起始位置为第一个元素, 终点为最后一个元素
        // 一列时, 同样起点为第一个元素, 终点为这一列最后一个元素

        // 这里是针对二维数组只有一个元素时, 直接返回这个元素
        if (m == 1 && n == 1) {
            return grid[0][0];
        }

        // 2. 初始化
        // 先将新增的第一行和第一列全部初始化为无穷大
        for (int j = 0; j <= n; j++) {
            dp[0][j] = Integer.MAX_VALUE;
        }
        for (int i = 0; i <= m; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }

        // 将起始位置的上方和前方初始化为 0
        dp[0][1] = dp[1][0] = 0;

        // 3. 填写 dp 表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 根据状态方程填写
                // 由于我们新开了一行一列. 此时的位置对应到grid 中下标要 - 1
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }

        // 4. 确认返回值
        return dp[m][n];
    }

    /**
     * 地下城游戏
     *
     * @param dungeon
     * @return
     */
    public int calculateMinimumHP(int[][] dungeon) {

        // 1. 创建 dp 表
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m + 1][n + 1];

        // 2. 初始化
        // 将最后一行初始化为无穷大
        for (int j = 0; j <= n; j++) {
            dp[m][j] = Integer.MAX_VALUE;
        }
        // 将最后一列初始化为无穷大
        for (int i = 0; i <= m; i++) {
            dp[i][n] = Integer.MAX_VALUE;
        }
        // 将终点的右边和下边位置初始化为 1
        dp[m][n - 1] = dp[m - 1][n] = 1;

        // 3. 填写 dp 表, 从下往上每一行, 每一行从右往左
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {

                // 根据状态转移方程填写
                // 虽然多开了一行一列, 但是对应到原本的 dungeon 的位置没变.
                // 因为添加的位置是在最后一行和最后一列.
                dp[i][j] = Math.min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j];

                // 如果最终的结果太小为负数, dp 表中表示某个位置为起点的最低初始血量至少大于 1
                // 因此要对这个最终结果进行处理
                dp[i][j] = Math.max(1, dp[i][j]);
            }
        }

        // 4. 确认返回值
        return dp[0][0];
    }

    /**
     * 按摩师
     *
     * @param nums 预约时长数组
     * @return 返回最长的预约时间
     */
    public int massage(int[] nums) {

        // 1. 创建 dp 表
        // 有两个状态表示, 需要两个 dp 表
        int n = nums.length;
        int[] f = new int[n]; // 表示预约 nums[i]
        int[] g = new int[n]; // 表示不预约 nums[i]

        // 特殊情况处理, 防止 f[0] 初始化越界
        if (n == 0) {
            return 0;
        }

        // 2. 初始化
        f[0] = nums[0];
        g[0] = 0;

        // 3. 填写 dp 表
        for (int i = 1; i < n; i++) {
            // 根据状态转移方程填写
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }

        // 4. 确认返回值
        return Math.max(f[n - 1], g[n - 1]);
    }

    /**
     * 打家劫舍问题
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {

        // 1. 创建 dp 表
        int n = nums.length;
        int[] f = new int[n]; // 偷窃到 i 位置时,偷窃 nums[i]
        int[] g = new int[n]; // 偷窃到 i 位置时, 不偷窃nums[i]

        // 2. 初始化
        f[0] = nums[0];
        g[0] = 0; // 可以不写, 数组不初始化默认为 0

        // 3. 填写 dp 表
        for (int i = 1; i < n; i++) {
            // 根据不同的状态转移方程填写
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }

        // 4. 确认返回值
        return Math.max(g[n - 1], f[n - 1]);

    }

    /**
     * 打家劫舍II 问题
     */
    public int robII(int[] nums) {

        int n = nums.length;
        // 返回两个子问题的 打家劫舍1 的最大值
        // 传入的是闭区间 [2, n-2] [1, n-1] 需要注意
        return Math.max(rob1(nums, 2, n - 2) + nums[0], rob1(nums, 1, n - 1));

    }

    private int rob1(int[] nums, int left, int right) {

        // 判断边界值
        if (left > right) return 0; // 此时数组不存在, 无法偷窃

        // 1. 创建 dp 表
        int n = nums.length;
        int[] f = new int[n]; // 表示偷窃到 i 位置时, 偷窃nums[i]
        int[] g = new int[n]; // 表示偷窃到 i 位置时, 不偷窃 nums[i]

        // 2. 初始化
        // 此时 left 为这个数组偷窃的第一个位置需要注意
        f[left] = nums[left];

        // 3. 填写 dp 表
        // left 位置已经初始化了, 从 left + 1 开始到 right 位置结束
        for (int i = left + 1; i <= right; i++) {
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }

        // 4. 确认返回值
        // 返回的是偷窃的数组的最后位置的最大值. 因此为 right
        return Math.max(g[right], f[right]);
    }

    /**
     * 删除节点并获得节点数
     *
     * @param nums
     * @return
     */
    public int deleteAndEarn(int[] nums) {

        // 1. 创建 dp 表
        int n = 10001; // 和预处理的数组一样大, 下标直接对应不需要考虑映射关系

        int[] f = new int[n]; // 从任意位置删除到 i 位置时, 选择 nums[i]时所获得的最大节点数
        int[] g = new int[n]; // 从任意位置删除到 i 位置时, 不选择 nums[i]所获得的最大节点数

        // 预处理 nums 数组让其下标连续对应 "打家劫舍" 问题
        int[] array = new int[n]; // 根据题目开辟足够大的空间存储
        for (int x : nums) {
            array[x] += x;
        }

        // 2. 初始化
        f[0] = array[0];

        // 3. 填写 dp 表
        for (int i = 1; i < n; i++) {
            // 根据不同的状态转移方程填写
            f[i] = g[i - 1] + array[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }

        // 4. 确认返回值
        return Math.max(f[n - 1], g[n - 1]);
    }

    /**
     * 最小花费粉刷房子
     *
     * @param costs
     * @return
     */
    public int minCost(int[][] costs) {

        // 1. 创建 dp 表
        int n = costs.length; // 一共有多少个房间
        int[][] dp = new int[n + 1][3]; // 里面存的是 const[i][j] 每个房间不同颜色的花费

        // 2. 初始化
        dp[0][0] = 0;

        // 3. 填写 dp 表
        for (int i = 1; i <= n; i++) {

            // 这里的 for(int j = 0; j < 3; j++) 可以不写, 因为每一行的 0 1 2 三列是题目固定的

            // 根据状态转移方程填写
            // 需要注意的是, 因为对开了一格, 原本 costs 数组 0 下标对应在新的 dp 表中的 1 位置.
            // 想要从 dp 表中找到原本在 costs 数组中的位置, 下标都需要 - 1
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];

        }

        // 4. 确认返回值
        return Math.min(Math.min(dp[n][0], dp[n][1]), dp[n][2]);
    }

    /**
     * 买卖股票的最佳时间
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {

        // 1. 创建 dp 表
        int n = prices.length;
        int[][] dp = new int[n][3];

        // 2. 初始化
        dp[0][0] = -prices[0];

        // 3. 填写 dp 表
        for (int i = 1; i < n; i++) {
            // 根据状态转移方程填写
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][0] + prices[i];
        }

        // 4. 确认返回值
        return Math.max(dp[n - 1][1], dp[n - 1][2]);
    }

    /**
     * 最佳股票买入时间 II
     *
     * @param prices
     * @param fee
     * @return
     */
    public int maxProfit(int[] prices, int fee) {

        // 1. 创建 dp 表
        int n = prices.length;
        int[] f = new int[n]; // i 位置结束时为买入状态所获得的最大利润
        int[] g = new int[n]; // i 位置结束时为卖出状态所获得的最大利润

        // 2. 初始化
        f[0] = -prices[0];

        // 3. 填写 dp 表
        for (int i = 1; i < n; i++) {
            f[i] = Math.max(g[i - 1] - prices[i], f[i - 1]);
            g[i] = Math.max(f[i - 1] + prices[i] - fee, g[i - 1]);
        }

        // 4. 确认返回值
        return Math.max(f[n - 1], g[n - 1]);
    }

    /**
     * 股票最佳买卖时机 III
     *
     * @param prices
     * @return
     */
    public int maxProfit3(int[] prices) {

        int MIN_VALUE = -0X3F3F3F3F;

        // 1. 创建 dp 表
        int n = prices.length; // 进入股市多少天

        // [n][3] 表示 n 天, 每天有三种交易情况
        int[][] f = new int[n][3]; // 第 i 天结束时, 交易了 j 次, 最终获得的最大利润
        int[][] g = new int[n][3]; // 第 i 天结束时, 交易了 j 次, 最终获得的最大利润

        // 2. 初始化
        // 2.1 先将第一行初始化为负无穷大
        for (int j = 0; j < 3; j++) {
            // f 表第一行以及 g 表第一行
            f[0][j] = g[0][j] = MIN_VALUE;
        }

        // 2.2 将 f 表中第一行第一个初始化
        f[0][0] = -prices[0];
        g[0][0] = 0;

        // 3. 填写 dp 表
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                // 根据状态转移方程填写
                // 填写 f 表
                f[i][j] = Math.max(g[i - 1][j] - prices[i], f[i - 1][j]);

                g[i][j] = g[i - 1][j]; // g 表第一步是必会发生的
                // 判断是否需要填写 g 表
                // g 表第二步符合条件才发生进行填写
                if (j - 1 >= 0) {
                    g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }

        // 4. 确认返回值
        int target = MIN_VALUE; // 不用 target 去比较判断最大值, 因此不需要赋值为负无穷

        // 遍历整个 g 表最后一行获取三种交易次数的最大利润
        for (int j = 0; j < 3; j++) {
            target = Math.max(target, g[n - 1][j]);
        }

        return target;

    }

    /**
     * 环绕字符串中唯一的子字符串
     *
     * @param ss
     * @return
     */
    public int findSubstringInWraproundString(String ss) {
        // 以 i 位置元素为结尾时的所有子串中在 base 里的出现的个数即 dp[i]
        // 以 i 位置元素为结尾的所有子串又分两种情况
        // 1. 长度为 1 即只有一个字符, 由于 s 中的字符全是小写英文字母, 单独时必然在base中存在

        // 2. 长度 > 1 时, 以最近一步划分问题, 考虑 i - 1, 以 i - 1 位置元素结尾有多少个在base中则有多少个以 i 元素结尾的元素在 base 中.
        // 结果为 dp[i - 1]. 但需要满足条件即 s[i - 1] + '1' = s[i]
        // 此处不需要 + 1, 因为dp[i] 表示的是在 base 中出现的子串个数. i - 1 为结尾的子串是以 i 为结尾的子串在 base 中的个数, 因此不需要 + 1

        // 返回值比较特殊, 需要进行一定的去重处理. 比如 y z a b c 和 a b c. 都以 c 为结尾, 但是 y z a b c 包含了 a b c 子串在 base 中存在的情况. 因此会出现重复情况, 因此只需要将 a - z 的字母对应映射到下标中进行最大的结果处理
        // 由于不同位置可能会出现重复位置, 因此需要取最大值
        // 即 hash[s[i] - 'a'] =  Math.max(hash[s[i] - 'a']], dp[i]); 因为越往后出现为结尾的的会包括前面的

        // 预处理
        char[] s = ss.toCharArray(); // 转为字符数组方便下标遍历

        // 1. 创建 dp 表
        int n = s.length;
        int[] dp = new int[n];

        // 2. 初始化
        // 最差情况为该字符本身, 一定存在在 base 中至少为 1
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }

        // 3. 填写 dp 表
        int[] hash = new int[26];

        // 根据状态转移方程填写
        for (int i = 1; i < n; i++) {
            // 符合条件时
            if (s[i - 1] + 1 == s[i] || (s[i - 1] == 'z' && s[i] == 'a')) {
                dp[i] += dp[i - 1];
            }
        }

        // 去重处理, 越往后出现的相同结尾位置存储的 base 中的子串个数越多
        for (int i = 0; i < n; i++) {
            hash[s[i] - 'a'] = Math.max(hash[s[i] - 'a'], dp[i]);
        }

        // 4. 确认返回值
        // dp 表中存的是每一个位置元素为结尾的所有子串在 base 中的个数. 因此遍历加和 dp 表即为所有
        int sum = 0;
        // 直接遍历 dp 表会重复, 需要遍历去重后的
        for (int x : hash) {
            sum += x;
        }

        return sum;
    }

    /**
     * 买卖股票的最佳时机 IV
     *
     * @param k
     * @param prices
     * @return
     */
    public int maxProfit(int k, int[] prices) {

        // 预处理
        int n = prices.length;
        int INF = -0X3F3F3F3F;
        k = Math.min(k, n / 2);

        // 1. 创建 dp 表
        // 虽然第一列不用初始化了, 但任然需要
        int[][] f = new int[n + 1][k + 1];
        int[][] g = new int[n + 1][k + 1];

        // 2. 初始化
        // 2.1 将 g 表和 f 表第一行同时初始化为负无穷大
        for (int j = 0; j < k + 1; j++) {
            f[0][j] = g[0][j] = INF;
        }
        // 2.2 对 f 表和 g 表第一行第一个位置单独处理
        f[0][0] = -prices[0];
        g[0][0] = 0;

        // 3. 填写 dp 表
        for (int i = 1; i < n + 1; i++) {
            for (int j = 0; j < k + 1; j++) {
                // 根据状态转移方程填写
                // 需要注意, 因为新开了一行相当于多了一天
                // 想要找到原本哪一天的价格, 就需要下标对应 - 1
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i - 1]);

                // 填写 g 表第一步
                g[i][j] = g[i - 1][j];

                // 符合条件才执行 g 表的第二步
                if (j - 1 >= 0) {
                    g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i - 1]);
                }
            }
        }

        // 4. 确认返回值
        int temp = INF;
        for (int j = 0; j <= k; j++) {
            // 这里新开了一行, 一共有 n + 1 天, 最后一天对应到下标为 n
            temp = Math.max(temp, g[n][j]);
        }

        return temp;
    }


    public void fun6() {
        Scanner scan = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String s = scan.nextLine();
        char[] arr = s.toCharArray();
        HashMap<Character, Integer> map = new HashMap<>();

        for (int i = 0; i < arr.length; i++) {
            // 如果首次加入, 则将其此处置为 1
            if (!map.containsKey(arr[i])) {
                map.put(arr[i], 1);
            } else {
                // 重复出现, 叠加其出现次数
                // 取出包含的 value 值
                int count = map.get(arr[i]);
                map.put(arr[i], count + 1);
            }
        }

        // 遍历数组, 通过 key 寻找 value 为 1 的
        boolean flag = true;
        for (int i = 0; i < arr.length; i++) {
            if (map.get(arr[i]) == 1) {
                flag = false;
                System.out.println(arr[i]);
                break;
            }
        }
        // 没有找到
        if (flag) {
            System.out.println(-1);
        }
    }

    /**
     * 求解字符串编辑距离
     *
     * @param s1 字符串1
     * @param s2 字符串2
     * @return 返回最短编辑距离
     */
    private static int len(char[] s1, char[] s2) {

        // dp[i][j] 表示从起始位置到字符串A的i位置以及字符串B的j位置的编辑距离

        // 状态转移方程
        // 以最近一步划分问题, 当 i 和 j 位置字符相同时, 比较他们前一个字符是否相同
        // 即 dp[i][j] = dp[i - 1][j - 1]

        // 当 i != j 时, 有两种情况, 并删除多出来的那个元素, 观察其前一个元素
        // 1. i - 1 和 j - 2 是否相同, dp[i][j] = dp[i][j - 1], 删掉 i - 1 位置
        // 2. i - 2 和 j - 1 是否相同, dp[i][j] = dp[i - 1][j]

        // 初始化
        // 有dp[i][j] 定义可以知道, 当i=0时, 表示只有一个字符串, 想要编辑只能编辑j的长度
        // dp[i][0] = i dp[0][j] = j

        // 遍历顺序, 从上到下每一行, 每行从左往右,

        int m = s1.length;
        int n = s2.length;
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;
            for (int j = 1; j <= n; j++) {
                dp[0][j] = j;

                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) throws NoSuchMethodException, InvocationTargetException, IllegalAccessException {
        //Training.sanjiao();

//        Scanner scan = new Scanner(System.in);
//        //String src = scan.nextLine();
//
//        HashMap<Character, Integer> map = new HashMap<>();
//        map.put('a', 1);
//        System.out.println(map.get('a'));

        //System.out.println(reverse(src));

//        int[] array = {5,2,7,3};
//        Training.bubbleSort(array);
//        System.out.println(Arrays.toString(array));

        //Training.fun7();

        List<Integer> list = new ArrayList<>();
        list.add(99);
        list.getClass().getMethod("add", Object.class).invoke(list, "reflect");
        System.out.println(list);


    }

    private static String reverse(String src) {
        char[] arr = src.toCharArray();

        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            char tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            left++;
            right--;
        }

        return Arrays.toString(arr);
    }


    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                }
            }
        }


    }

    public int maxSubarraySumCircular(int[] nums) {
        // 状态表示 以 i 位置为结尾时的所有子数组的最大子数组和或者最小子数组和
        // f[i] = 以 i 为结尾的最大子数组和   g[i] = 以 i 为结尾的最小子数组和
        // f[i] = max(nums[i], nums[i] + f[i-1])
        // g[i] = min(nums[i], nums[i] + g[i-1])

        // // 1. 创建 dp 表
        // int n = nums.length;
        // int[] f = new int[n + 1];
        // int[] g = new int[n + 1];

        // // 2. 初始化
        // f[0] = 0;
        // g[0] = 0;

        // // 3. 填写 dp 表
        // int sum = 0;
        // int fmax = Integer.MIN_VALUE;
        // int gmin = Integer.MAX_VALUE;

        // for(int i = 1; i <= n; i++) {

        //     f[i] = Math.max(nums[i - 1], nums[i - 1] + f[i - 1]);
        //     fmax = Math.max(fmax, f[i]);

        //     g[i] = Math.min(nums[i - 1], nums[i - 1] + g[i - 1]);
        //     gmin = Math.min(gmin, g[i]);

        //     sum += nums[i - 1];
        // }

        // // 4. 确认返回值
        // return sum == gmin ? fmax : Math.max(fmax, sum - gmin);

        // 因为是环形子数组, 求解环形部分的子数组最大和为整个数组的和 muns 减去除环形部分外的最小值的和 g[i]

        // f[i] : 表示以 i 位置为结尾时的子数组最大和
        // g[i] : 表示以 i 位置为结尾时的子数组最小和

        // 状态转移方程推导 :
        // 在数组区间内时, 长度为 1 , 则环形子数组最大和为 nums[i]
        //                长度为大于 1 时, 则环形子数组最大和为 nums[i] + f[i - 1]
        // 最终 f[i] = Math.max(nums[i], nums[i] + f[i - 1])

        // 在环形区间内, 则求解该数组的子数组和, 整个数组的和减去最小子数组和即为环形数组的最大和
        // 长度为 1 时, 最小子数组和为 nums[i]
        // 长度大于 1 时, 最小子数组为 nums[i] + g[i - 1]
        // 最终 g[i] = Math.min(nums[i], nums[i] + g[i - 1])

        // 1. 创建 dp 表
        int n = nums.length;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];

        // 2. 初始化
        // i = 1 时, 为了不影响最终结果, 一次 g[i - 1] = g[0] = 0, 此时不影响最终结果为 nums[1]

        // 3. 填写 dp 表
        int sum = 0; // 统计整个数组和
        int fmax = Integer.MIN_VALUE; // 统计最大和
        int gmin = Integer.MAX_VALUE; // 统计最小和

        for (int i = 1; i < n + 1; i++) {
            // 填写 f 表
            f[i] = Math.max(nums[i - 1], nums[i - 1] + f[i - 1]);
            // 填写 g 表
            g[i] = Math.min(nums[i - 1], nums[i - 1] + g[i - 1]);

            sum += nums[i - 1];

            fmax = Math.max(fmax, f[i]);
            gmin = Math.min(gmin, g[i]);
        }

        // 4. 确认返回值
        // 此时已经找到了整个数组之内的子数组最大和, 以及环形子数组最小值(利用总和求解环形子数组最大和)
        // 如果这样返回, 当全是负数时, sum - gmin = 0;
        // 而此时 gmax 也是最小那个负数, 最终返回结果是 0, 但正确结果应该是 gmax 里存的最小的负数
        // return gmax > sum - gmin ? gmax : sum - gmin;

        // 因此需要判定 sum - gmin = 0 全是负数的情况, 返回 gmax, 否则返回两种情况最大值
        return sum - gmin == 0 ? fmax : Math.max(fmax, sum - gmin);
    }


    /**
     * 删除相同值的节点 -- 直接比较删除
     */
    public listNode deleteDuplicates(listNode head) {
        if (head == null) {
            return null;
        }

        // 设定虚拟节点
        listNode res = new listNode(-1);
        res.next = head;
        listNode cur = res;
        while (cur.next != null && cur.next.next != null) {
            // 判断节点是否相等
            if (cur.next.val == cur.next.next.val) {
                int temp = cur.next.val;
                while (cur.next != null && cur.next.val == temp) {
                    // 跳过这个节点
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }

        return res.next;
    }

    /**
     * 删除相同的所有节点, 返回只出现一次的节点. 利用 Hash 表进行标记处理
     *
     * @param head
     * @return
     */
    public listNode deleteDuplicates1(listNode head) {

        if (head == null) {
            return null;
        }

        Map<Integer, Integer> map = new HashMap<>();
        listNode cur = head;
        while (cur != null) {
            // 多次出现, 每次出现次数加 1
            if (map.containsKey(cur.val)) {
                map.put(cur.val, map.get(cur.val) + 1);
            } else {
                // 首次出现, 设为 1
                map.put(cur.val, 1);
            }
            cur = cur.next;
        }
        // 增设虚拟节点
        listNode res = new listNode(0);
        res.next = head;
        // 重置 cur 从虚拟节点开始, 避免需要删除头结点的情况
        cur = res;
        // 再次遍历节点, 和Hash表中存的结果毕竟, 如果出现次数大于1就删除
        while (cur.next != null) {
            if (map.get(cur.next.val) != 1) {
                // 不止出现一次, 删除
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return res.next;
    }

    /**
     * 合并两个有序数组
     *
     * @param nums1 有序数组 1 大小为 m + n
     * @param m     nums1 的有效元素 为 m 个
     * @param nums2 有序数组 2
     * @param n     num2 的有效元素为 n 个
     * @return 返回合并后的有序数组
     */
    public int[] merge(int[] nums1, int m, int[] nums2, int n) {
        // m 为 nums1 的有效个元素
        // n 为 nums2 的有效个元素
        for (int i = m + n - 1; i >= 0; i--) {
            if (n == 0 || m == 0) {
                break;
            }
            if (nums1[m - 1] <= nums2[n - 1]) {
                nums1[i] = nums2[n - 1];
                n--;
            } else {
                nums1[i] = nums1[m - 1];
                m--;
            }

        }

        return nums1;
    }


    /**
     * 最长湍流子数组问题
     */
    public int maxTurbulenceSize(int[] arr) {

        // 1. 创建 dp 表
        int n = arr.length;
        int[] g = new int[n];
        int[] f = new int[n];
        // 2. 初始化
        // 最差情况下, 可以以自身单独为一个湍流子数组, 长度为 1
        for (int i = 0; i < n; i++) {
            g[i] = 1;
            f[i] = 1;
        }

        // 3. 填写 dp 表
        int ret = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i - 1] > arr[i]) {
                g[i] = f[i - 1] + 1;
            } else if (arr[i - 1] < arr[i]) {
                f[i] = g[i - 1] + 1;
            }

            ret = Math.max(ret, Math.max(f[i], g[i]));
        }

        // 4. 确认返回值
        // g表和f表中都存了不同位置的子数组中的湍流数组的最长长度, 因此需要遍历两张表找最大值
        return ret;
    }

    /**
     * 最长递增子序列个数问题
     */
    public int findNumberOfLIS(int[] nums) {
        // dp[i] 以 i 位置为结尾时的所有子序列中, 最长递增子序列的个数

        // len[i] 以 i 位置为结尾的所有子序列中, 最长递增子序列的长度
        // count[i] 以 i 位置为结尾时所有子序列中, 最长递增子序列的个数

        // 对于 len[i] 即求解最长递增子序列长度, 划分为两种情况.
        // i 位置单独为一个递增子序列, 长度为 1
        // i 位置和 j [0, i - 1] 结合形成最长递增子序列, 因此要求以 j 位置为结尾的所有子序列中最长的递增子序列, 前提条件时递增, 即 : nums[j] < nums[i]

        // 当知道 len[i] 每个位置的最长递增子序列的长度后, 则可以进行统计个数
        // 当只有一个元素时, 自身构成最长递增子序列, 个数为 1
        // 当元素大于一个时, 最长递增子序列个数为 i + j 位置[0, i - 1] 之间最长递增子序列的长度. 即 len[j] + 1.

        // 当 len[j] + 1 == len[i] 说明以 i 位置元素为结尾的个数此时同 j 位置和 i 位置组合起来的最长递增子序列长度相等. 此时只需要更新 i 位置的最长递增子序列个数为 count[i] += count[j] 即可.
        // 当 len[j] + 1 < len[i], 说明以 i 位置元素为结尾的个数此时同 j 位置和 i 位置组合起来的最长递增子序列长度还要大, 则没必要更新. 忽略当前 j 和 i 组合的个数.
        // 当 len[j] + 1 > len[i], 说明以 i 位置元素为结尾的个数此时同 j 位置和 i 位置组合起来的最长递增子序列个数还要小, 则需要将 i 位置的最长递增子序列个数更新为 j 和 i 位置组合的长度. 即 len[i] = len[j] + 1, 然后重新计数. 此时 j 位置就是最长递增子序列 在更新个数为当前 j 位置的个数. count[i] = count[j];

        // 1. 建立 dp 表
        int n = nums.length;
        int[] len = new int[n];
        int[] count = new int[n];

        // 2. 初始化
        for (int i = 0; i < n; i++) {
            len[i] = count[i] = 1;
        }

        // 3. 填写 dp 表
        // 3.1  0 下标位置代表只有一个元素, 此时 len[0] 和 count[0] 都是 1
        int maxLen = 1; // 最差都是以自己为递增子序列, 长度和个数都为 1
        int maxCount = 1;
        for (int i = 1; i < n; i++) {
            // 确认 j 的范围为 [0, i - 1]
            for (int j = 0; j < i; j++) {
                // 递增的条件下
                if (nums[j] < nums[i]) {
                    // 根据长度来决定是否更新个数.
                    if (len[j] + 1 == len[i]) {
                        count[i] += count[j];
                    } else if (len[j] + 1 > len[i]) {
                        // 更新长度
                        len[i] = len[j] + 1;
                        // i 位置长度发生该表, 其对应个数也会发生改变. 此时相当于重新计数
                        count[i] = count[j];
                    }
                }
            }

            if (maxLen == len[i]) {
                // 此时可能是 i 位置结尾时出现的递增子序列最大的个数, 统计即可.
                maxCount += count[i];
            } else if (maxLen < len[i]) {
                // 当前的长度不是最大值, 遇到了 i 位置更大, 则更新长度重新计数
                maxLen = len[i];
                maxCount = count[i];
            }
        }

        // 4. 确认返回值
        // len[i] 存了以 i 位置为结尾的所有最长递增子序列的长度. ( 但可能以 i 位置为结尾的最长递增子序列不止一个 ), 因此需要通过遍历每个位置来寻找对应的 count[i] 的最大值

        // 找 len 的最大值. 并统计最大值长度出现的个数.
        return maxCount;
    }

    /**
     * 最长数对链 - 最长递增子序列变种
     */
    public int findLongestChain(int[][] pairs) {
        // 1. 题目分析 : 类似与之前的最长递增序列长度. 但不同的是, 这里的数对并非有序的. 也就是说实例 2 的情况, 选择第一对数对后, 可以选择第三对数对在选择第二对. 可以任意挑选, 并非有序的. 但填表顺序必须是线性的, 从左往右/从右往左. 随机的填表顺序难以完成. 因此需要预处理.
        // 那么, 如何让数对变的有序, 因此就需要对数对提前进行排序. 根据每个数对中的第一个数进行排序.  当 pairs[i] > pairs[i + 1], pairs[i + 1] > pairs[i + 2], 那么pairs[i]必定大于pairs[i + 2]

        // dp[i] 表示以 i 位置为结尾时的所有数对连中, 最长的数对链的长度.

        // 状态转移方程 : 还是两种情况
        // 1. 以 i 位置自身构成数对链. 最终数对链长度为 1
        // 2. 以 i 位置和 j[0, i - 1] 位置的数对链构成最长数对链. 那么就要求 j 在[0, i - 1]中是最长的数对链长度. 并且还需要满足递增, 即 dp[j] 位置的第2 个元素 pairs[j][1] < i 位置的第一个元素即 pairs[i][0], 因此最终 dp[i] = Math.max(dp[j] + 1, dp[i]);
        // 3. 初始化. 数对链长度最短为 1, 因此初始化为 1.
        // 4. 填表顺序为从左往右顺序填写

        // 预处理排序变为顺序填表, 这里并不能直接用排序整个数组. 因为数组里的类型是整型数组. 因此我们通过整形数组的第一个元素来进行比较
        // a[0] - b[0] < 0 => a 在 b 之前.
        // a[0] - b[0] == 0  => a b 位置不变
        // a[0] - b[0] > 0 => a 在 b 之后
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);

        // 1. 建立 dp 表
        int n = pairs.length;
        int[] dp = new int[n];
        // 2. 初始化
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        // 3. 填写 dp 表
        int maxLen = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // 符合递增时
                if (pairs[j][1] < pairs[i][0]) {
                    // 填写 dp 表
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        // 4. 确认返回值
        // dp 表中存着每个位置为结尾时的最长数对链长度, 因此任何位置都有可能是最长的, 遍历整个数组寻找最大值
        return maxLen;
    }

    public static int fun7() {
        throw new RuntimeException();
    }

    public static void main3(String[] args) {
//        String[] arr = {"a","bc"};
//        String[] a = Arrays.toString(arr).split(",");
//        for (int i = 0; i < a.length; i++) {
//            System.out.println(a[i]);
//        }

//          Training training = new Training();
//          training.fun(training.arr);
//        System.out.println(training.arr);

//        int x, y;
//        x = 5 >> 2;
//        System.out.println(x);
//        y = x >>> 2;
//        System.out.println(y);

//        boolean b = true ? false :true == true ? false: true;
//        System.out.println(b);
//        long c = 012;
//        double x = 3.0;
//        int y = 5;
//        System.out.println(x /= --y);
//        String a = "ss";
//        String b = "ssa";
//        System.out.println(a.compareTo(b));
        Training training = new Training();
        //training.fun3();
        //training.test();
        char[] arr = {'1', '2', '3'};
        System.out.println(arr);

    }

//    public void add(byte b) {
//        b = b++;
//    }
//    public void test() {
//        Byte a = 127;
//        Byte b = 127;
//        add(++a);
//        System.out.println(a + " ");
//        add(b);
//        System.out.println(b + " ");
//    }
}

// 创建链表
class listNode {
    public int val;
    public listNode next;

    // 提供构造方法
    public listNode(int val) {
        this.val = val;
    }
}

